<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Two Ways of Specifying Constraint Behaviours
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial109.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc212">15.1</A>&nbsp;&nbsp;Two Ways of Specifying Constraint Behaviours</H2>
There are two elegant and simple ways of building constraints
available in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>, called <EM>Propia</EM> and <EM>Constraint
Handling Rules</EM> (or <EM>CHR</EM>'s). 
They are themselves built using the facilities
described in chapter <A HREF="tutorial098.html#chapimpl">14</A>.<BR>
<BR>
<A NAME="@default381"></A>
Consider a simple <EM>noclash</EM> constraint requiring that two
activities cannot be in progress at the same time. 
For the sake of the example, the constraint involves two variables,
the start times <I>S</I>1 and <I>S</I>2 
of the two activities, which both have duration 5.
Logically this constraint states that
<EM>noclash</EM> &#8660; (<I>S</I>1 &gt;= <I>S</I>2 + 5 &or; <I>S</I>2 &gt;= <I>S</I>1 + 5).
The same logic can be expressed as two ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> clauses:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
noclash(S1,S2) :-
    ic:(S1 $&gt;= S2+5).
noclash(S1,S2) :-
    ic:(S2 $&gt;= S1+5).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Constraint propagation elicits information from constraints without
leaving any choice points. Constraint propagation behaviour can be
associated with each of the above representations, by CHR's
and by Propia.<BR>
<BR>
One way to propagate information from <EM>noclash</EM> is to wait until
the domains of the start times are reduced sufficiently that only one
ordering of the tasks is possible, and then to enforce the constraint
that the second task not start until the first is finished.<BR>
<BR>
<A NAME="@default382"></A>
This behaviour can be implemented in CHR's as follows:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- constraints noclash/2.
noclash(S1,S2) &lt;=&gt; ic:(S2 #&lt; S1+5) | ic:(S1 #&gt;= S2+5).
noclash(S1,S2) &lt;=&gt; ic:(S1 #&lt; S2+5) | ic:(S2 #&gt;= S1+5).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Consider the query:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?- ic:([S1,S2]::1..10),
   noclash(S1,S2),
   S1 #&gt;= 6.
</PRE></BLOCKQUOTE>
In this query <EM>noclash</EM> achieves no propagation when it is
initially posted with the start time domains set to <CODE>1..10</CODE>.
However, after imposing <I>S</I>1&gt;=6, 
the domain of <I>S</I>1 is reduced to <CODE>6..10</CODE>.
Immediately the <EM>noclash</EM>
constraint wakes, detects that the first
condition <I>S</I>1+5 &gt;= <I>S</I>2 is entailed, 
and narrows the domain of <I>S</I>2 to <CODE>1..5</CODE>.<BR>
<BR>
The same behaviour can be expressed in Propia, but this time the
original ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> representation of <EM>noclash</EM> as two clauses is
used directly. The propagation behaviour is automatically
extracted from the two clauses by Propia when the <EM>noclash</EM> goal
is annotated as follows:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?-      [S1,S2]::1..10,
        noclash(S1,S2) infers most,
        S1 #&gt;= 6.
</PRE></BLOCKQUOTE>


	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
Propia and CHRs make it easy to turn the logical statement of a
constraint into code that efficiently enforces that constraint.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 15.1: Building Constraints without Tears</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial109.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
